home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / BBS-Archive / DiskUtil / Crunch / XPK.lha / XPK / DEVELOPER / RDCN / DECOMPR.ASM < prev    next >
Assembly Source File  |  1993-05-01  |  8KB  |  225 lines
  1. ;---------------------------------------------------------------------------;
  2. ;                                        ;
  3. ; This is the Ross Data Compression implemented in 68000 assembler          ;
  4. ; by Niklas Sjöberg, 2:203/415.3@Fidonet                    ;
  5. ;                                        ;
  6. ;                                        ;
  7. ; The source is fully in the Public Domain. If you think you can improve    ;
  8. ; some parts, feel free to modify the code. HOWEVER, be carefull to comment ;
  9. ; the parts where you change!                            ;
  10. ;                                        ;
  11. ; On entry:                                    ;
  12. ; a0 points to XpkSubParams                            ;
  13. ;---------------------------------------------------------------------------;
  14. ; 921205 - Due to optimization comments may seem a bit weird.. Just try
  15. ;          to read 5-10 lines at the time I'm sure you'll get it right..
  16. ; 930319 - Some optimizations by John Harris - jharris@cup.portal.com
  17. ;          All new opts marked with a '@'.  Cycle savings at 68000 level:
  18. ;          mloop is 8-10 cycles faster
  19. ;          path to s_loop is 18 cycles faster (outside the loop)
  20. ;           sr_loop is 32 cycles faster (outside)
  21. ;                  lr_loop is about 172 cycles faster, plus loop was changed to
  22. ;                          .l for 50 cycles faster every 4 bytes past cnt=23
  23. ;                  rl_loop is about 186 cycles faster, plus if src & dest are
  24. ;               either both even or both odd, the loop will use .l
  25. ;               for 58 cycles faster for every 4 bytes past cnt=19
  26. ; 930409 - (Niklas Sjoberg) Fixed some lethal bugs. Might take a few more
  27. ;          cycles but decompression won't be safe otherwise!
  28. ; 930418 - (John Harris) There were ways to fix the bugs in the routine
  29. ;          without losing any cycles.  Some other things had been changed by
  30. ;          Niklas, that have been put back to the way I originally wrote them.
  31. ;        - In Niklas's translation of my code, a couple of inadvertant changes
  32. ;          were made that caused the routine to break on the 68000.  These were
  33. ;          restored.  This will restore the speed to its full potential as well.
  34. ;        - Fixed one additional guru
  35.  
  36.     xdef _unpack            ; The only function called from
  37.                     ; the C-part of the library
  38.  
  39.     INCLUDE "libraries/xpksub.i"
  40.  
  41.     section    code
  42.  
  43. _unpack
  44.  
  45.     movem.l    a2-a6/d2-d7,-(SP)
  46.     move.l    xsp_InBuf(a0),a1    ; source pointer
  47.     move.l    xsp_InLen(a0),d1    ; source len
  48.     move.l    xsp_OutBuf(a0),a2    ; destination
  49.  
  50.     move.l    a1,a3            ; inbuff_idx  = inbuff
  51.     move.l    a2,a4            ; outbuff_idx = outbuff
  52.     move.l    a1,a5            ; inbuff_end  = inbuff
  53.     adda.l    d1,a5            ; + inbuff_len
  54.  
  55.     moveq    #0,d0
  56.     moveq    #0,d2
  57.     moveq    #0,d3
  58.     moveq    #0,d4
  59.     moveq    #0,d5
  60.     moveq    #0,d6
  61.     moveq    #0,d7
  62.     bra.s    mloop            ; @ New line.  mloop was restructured
  63. ;                ;to remove one branch, and adjust the others to
  64. ;                ;fall through most often instead of branching.
  65.  
  66. ;                               ; loopend moved here to make 1 branch short
  67. loopend
  68.     suba.l    a2,a4            ; This is the only exit point
  69.     move.l    a4,xsp_OutBufLen(a0)    ; return length to xpkmaster
  70.     movem.l    (SP)+,a2-a6/d2-d7
  71.     moveq    #0,d0
  72.     rts
  73.  
  74. new_ctrlbits                            ; @ New label, and moved routine
  75. ;    move.w    (a3)+,d2        ; new load ctrl-bits
  76.     move.b    (a3)+,-(SP)        ; Slightly faster than shifting
  77.     move.w    (SP)+,d2        ; and works on 68000....
  78.     move.b    (a3)+,d2
  79.                     ;
  80.     moveq    #15,d3            ; ctrl_mask = 0x8000
  81. ; This is ugly. Since (in worst case) we may overrun the buffer by
  82. ; 15 bytes by not checking source and source-end. However, empty
  83. ; control-word means that we only copy 15 in worst case. Hell, we
  84. ; have 256 XPK_MARGIN bytes to play with :=) (I hope...)
  85.     cmp.l    a5,a3            ; main-loop. Go on until end of
  86.     bge.s    loopend            ; source buffer
  87.     btst    d3,d2                   ; @ These two lines are duplicated
  88.     bne.s    crunched        ;   for branch efficiency
  89.  
  90. copy_char                ; @ New label
  91.     move.b    (a3)+,(a4)+        ; otherwise, copy char and advance
  92. ;    bra.s    mloop            ; @ This line removed
  93. mloop
  94.     subq.b    #1,d3
  95. ;    lsr.w    #1,d3            ; Check if we need to get a load of
  96.                     ; control bits
  97.     bmi.s    new_ctrlbits        ; @ Changed branch priority
  98.  
  99. ;    move.w    d2,d7            ; If bits & mask turns out to be one
  100. ;    and.w    d3,d7            ; then data is compressed
  101.     btst    d3,d2
  102.     beq.s    copy_char               ; @ Changed branch priority
  103.  
  104. crunched
  105. ;                ;@d4 only needs to be word extended for s_loop,
  106. ;                ;so I removed moveq #0 and added ext.w at s_loop
  107.  
  108. ;    moveq    #0,d4            ; First find out what compressions method
  109.                     ; that was used.
  110.     move.b    (a3)+,d4        ; d4 will eventually contain 0-15
  111.     move.w    d4,d5            ; d5, contains count (further count may
  112.     and.w    #$f,d5            ; @ (.w)   be needed for some methods.
  113.     lsr.b    #4,d4            ; The higher 4 bits of d4 is type, and
  114. ;    and.w    #$f,d4            ; the lower count
  115.  
  116. ;    cmpi.b    #2,d4            ; @cmd > 2 then it's a short pattern
  117.     subq.b    #2,d4            ; @subq is faster than cmpi -- we just
  118. ;                    ;  have to adjust two later uses
  119.     bls.s    no_spat            ; (3-15)
  120. ;    move.w    d5,d6            ; count is 3 chars higher actually
  121.     addq.b    #3,d5            ; d5 is never >15+3
  122.     moveq    #0,d7            ; to use d4 as loop-register
  123.     move.b    (a3)+,d7        ; decode offset
  124.     asl.w    #4,d7
  125.     add.w    d5,d7
  126.     move.l    a4,a6            ; Next copy d4 characters from a6
  127.     sub.l    d7,a6            ; to a4
  128. ;    subq.b    #1,d4            ; @
  129. ;                    ; @ This line would get adjusted to
  130. ;                    ;   addq #1 to compensate for subq #2,
  131.     move.b    (a6)+,(a4)+        ; @ but I'll just add one unrolled move
  132. ;                    ;   which does the same thing, faster
  133.     ext.w    d4            ; @ since earlier moveq was removed
  134. s_loop    move.b    (a6)+,(a4)+        ;
  135.     dbf    d4,s_loop
  136.     bra.s     mloop            ; Jump to main loop
  137.  
  138.  
  139. no_spat    addq.b    #1,d4            ; @ d4 now equals -1, 0, or 1.  All
  140. ;                    ;   further checks can be made with
  141. ;                                       ;   no more compares needed.
  142.     bpl.s    no_srle            ; @ d4=-1 for srle
  143. ;    addq.b    #2,d5            ; @Remove   cnt += 3 (-1 for dbf loop)
  144.     move.b    (a3)+,d7        ; char to repeat d5 times
  145.     move.b    d7,(a4)+        ; @ Replaced addq.b #2 with two unrolled
  146.     move.b    d7,(a4)+        ;   moves.  2 bytes longer, but faster
  147. sr_loop    move.b    d7,(a4)+        ;   since we save 2 loop iterations
  148.     dbf    d5,sr_loop
  149.     bra.s    mloop            ; Main loop
  150.  
  151.  
  152. no_srle                    ; @ remove cmp #1
  153.     bne.s    no_lrle
  154.     moveq    #0,d7                   ; d4=0 for lrle
  155.     move.b    (a3)+,d7        ; if so, decode high/low count
  156.     asl.w    #4,d7            ; and add them since long RLE
  157.     add.w    d7,d5            ; is least 19 :
  158.  
  159. ;    addi.w    #18,d5            ; @ Remove   cnt +=19 (-1 for dbf loop)
  160.  
  161.     move.b    (a3),d7            ; @ Build d7 to longword size
  162.     lsl.w    #8,d7            ; @
  163.     move.b    (a3)+,d7        ; char to set
  164.     move.w    d7,d4            ; @
  165.     swap    d7            ; @
  166.     move.w    d4,d7            ; @ d7 has chr duplicated in all 4 bytes
  167.     move.w    a4,d4            ; @ Get a4 to an even adr, so we can
  168.     lsr.b    #1,d4            ; @ use move.l's.
  169.     bcc.s    a4_even            ; @
  170.     move.b    d7,(a4)+        ; @ a4 was odd, so move one odd byte
  171.     subq.w    #1,d5            ; @ ** Bug Alert **
  172. ;                    ;   If d5 was 0, it will be MI now,
  173. ;                    ;   and will have to be handled later.
  174. a4_even    move.l    d7,(a4)+        ; @ ok, ok, this looks kinda wasteful
  175.     move.l    d7,(a4)+        ; @ Move 18 unrolled bytes to replace
  176.     move.l    d7,(a4)+        ; @ addi.w #18,d5
  177.     move.l    d7,(a4)+        ; @ I wanted this as fast as possible
  178.     move.w    d7,(a4)+        ; @ and I hope no one misses 6 bytes
  179.     move.w    d5,d4            ; @
  180.     bmi.s    done19            ; @ Bug fix - d5<0 can only occur if an
  181. ;                    ;   RLE length 19 occured on an odd adr.
  182. ;                    ;   In this case, 19 bytes have already
  183. ;                    ;   been moved.  Last bug I hope.
  184.     and.w    #3,d4            ; @ d4 = d5 modulo 4
  185.     lsr.w    #2,d5            ; @ Adj d5 for move.l loop
  186.     subq.w    #1,d5            ; @
  187.     bmi.s   lr_lp2            ; @ If d5<4
  188. lr_loop    move.l    d7,(a4)+        ; @ (.l)
  189.     dbf    d5,lr_loop
  190. lr_lp2    move.b    d7,(a4)+        ; @ Finish remainder of cnt
  191.     dbf    d4,lr_lp2        ; @
  192. done19    moveq    #0,d7            ; @ Clear top half of d7 again
  193.     bra.w    mloop            ; @ (.w) Main loop
  194.  
  195.  
  196. no_lrle                    ; only one case left, long pattern
  197.     move.w    d5,d6            ;
  198.     addq.w    #3,d6            ; at least 3 chars long pattern
  199.     moveq    #0,d7
  200.     move.b    (a3)+,d7        ; Decode and add high and low
  201.     asl.w    #4,d7            ; offset
  202.     add.w    d7,d6            ;
  203.     moveq    #0,d5
  204.     move.b    (a3)+,d5        ; Next, get count
  205.     addi.w    #15,d5            ; which is at least 16 (-1 for loop)
  206.     move.l    a4,a6            ; source
  207.     sub.l    d6,a6            ; destination
  208.         lsr.b    #1,d6            ; @ If difference between a6&a4 is odd,
  209.     bcs.s    rl_lp2            ; @ they are not on same boundary
  210.     move.w    a6,d6            ; @ Otherwise, we can opt with move.l
  211.         lsr.b    #1,d6            ; @
  212.     bcc.s    a6_even            ; @
  213.     move.b    (a6)+,(a4)+        ; @ Move odd byte so both adrs are even
  214.     subq.w    #1,d5            ; @ and adj count
  215. a6_even    move.w    d5,d4            ; @
  216.     and.w    #3,d5            ; @ d5 = d5 modulo 4
  217.     lsr.w    #2,d4            ; @ Adj d4 for move.l loop
  218.     subq.w    #1,d4            ; @
  219. rl_loop    move.l    (a6)+,(a4)+        ; @
  220.     dbf    d4,rl_loop        ; @
  221. rl_lp2    move.b    (a6)+,(a4)+        ; @
  222.     dbf    d5,rl_lp2        ; @
  223.     bra.w    mloop
  224.     END
  225.